package main

/*
给定一个n个元素有序的（升序）整型数组nums 和一个目标值 target ，写一个函数搜索nums中的 target，

如果目标值存在返回下标，否则返回 -1。
*/
func main() {
	nums := []int{-1, 0, 3, 5, 9, 12}
	target := 9
	print(search(nums, target))

}

/**
 *	search
 *	@Description:
 *	@param num []int
 *	@param target int
 *	@return int
 */
func search(nums []int, target int) int {
	right := len(nums) - 1
	left := 0
	return recursive(nums, left, right, target)
}

/**
 *	recursive
 *	@Description: 递归 打散
 *	@param num []int
 *	@param left int
 *	@param right int
 *	@param target int
 *	@return int
 */
func recursive(nums []int, left, right, target int) int {

	if right-left == 1 || right-left == 0 {
		if nums[left] == target {
			return left
		} else if nums[right] == target {
			return right
		} else {
			return -1
		}
	}
	mid := (left + right) >> 1
	if nums[mid] == target {
		return mid
	} else if nums[mid] > target {
		return recursive(nums, left, mid, target)
	} else {
		return recursive(nums, mid, right, target)
	}
}
